This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
In threshold cryptosystems, private keys are shared among n entities (also called “servers”) so as to avoid single points of failure. As a result, at least t≤n entities must contribute to the decryption process. When modeling the security, one distinguishes static adversaries, who have to decide which entities they want to corrupt before seeing the public key, from strictly stronger adaptive adversaries, who can decide whom to corrupt depending on the previously collected information.
More formally, a non-interactive (t,n)-threshold cryptosystem is a set of algorithms with these specifications.
Setup (λ, t, n): given a security parameter λ and integers t, nϵpoly(λ) (with 1≤t≤n) denoting the number of decryption entities n and the decryption threshold t, this algorithm outputs (PK, VK, SK), where PK is the public key, SK=(SK1, . . . , SKn) is a vector of private-key shares and VK=(VK1, . . . , VKn) is a vector of verification keys. Decryption entity i is given the private key share (i, SKi). For each iϵ{1, . . . , n}, the verification key VKi will be used to check the validity of decryption shares generated using SKi.Encrypt (PK,M): is a randomized algorithm that, given a public key PK and a plaintext M, outputs a ciphertext C.Ciphertext-Verify (PK,C): takes as input a public key PK and a ciphertext C. It outputs 1 if the ciphertext C is deemed valid with regard to the public key PK, and 0 otherwise.Share-Decrypt (PK, i, SKi, C): on input of a public key PK, a ciphertext C and a private-key share (i, SKi), this (possibly randomized) algorithm outputs a special symbol (i,⊥) if Ciphertext-Verify (PK, C)=0. Otherwise, it outputs a decryption share μi=(i,{circumflex over (μ)}i).Share-Verify (PK, VKi, C, μi): takes in a public key PK, the verification key VKi, a ciphertext C and a purported decryption share μi=(i,{circumflex over (μ)}i). It outputs either 1 or 0. In the former case, μi is said to be a valid decryption share. In the following, the convention that (i,⊥) is an invalid decryption share is adopted.Combine (PK, VK, C, {μi}iϵS): given a public key PK, the verification key VK, a ciphertext C and a subset S⊂{1, . . . , n} of size t=|S| with decryption shares {μi}iϵS, this algorithm outputs either a plaintext M or, if the set contains invalid decryption shares, ⊥.
Further descriptions of threshold cryptosystems may be found in:    Y. Desmedt. Society and Group Oriented Cryptography: A New Concept. In Crypto'87, Lecture Notes in Computer Science 293, pp. 120-127, Springer, 1987.    Y. Desmedt, Y. Frankel. Threshold Cryptosystems. In Crypto'89, Lecture Notes in Computer Science 435, pp. 307-315, Springer, 1989.    C. Boyd. Digital Multisignatures. In Cryptography and Coding (H. J. Beker and F. C. Piper Eds.), Oxford University Press, pp. 241-246, 1989.
As will be described hereinafter, further developments have been made to threshold schemes.
Schemes Resisting Static Corruptions
Chosen-ciphertext security (Indistinguishability under Chosen Ciphertext Attack, IND-CCA) is widely recognized as the standard security notion for public-key encryption. Securely distributing the decryption procedure of CCA-secure public-key schemes has been a challenging task. The difficulty is that decryption entities should return their partial decryption results before knowing whether the incoming ciphertext is valid and, in some cases, partial decryptions of ill-formed ciphertexts may leak useful information to the adversary. For this reason, it is difficult to “thresholdize” the original Cramer-Shoup system [R. Cramer, V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Crypto'98, Lecture Notes in Computer Science 1462, pp. 13-25, Springer, 1998.] because the validity of ciphertexts cannot be publicly verified.
The first solution to this problem was put forth by Shoup and Gennaro [V. Shoup, R. Gennaro. Securing Threshold Cryptosystems against Chosen Ciphertext Attack. In Journal of Cryptology, 15(2), pp. 75-96, 2002. Earlier version in Eurocrypt'98, Lecture Notes in Computer Science 1403, pp. 1-16, Springer, 1998.]: it requires the random oracle model and assumes static corruptions. In the standard model, Canetti and Goldwasser [R. Canetti, S. Goldwasser. An Efficient Threshold Public Key Cryptosystem Secure Against Adaptive Chosen Ciphertext Attack. In Eurocrypt'99, Lecture Notes in Computer Science 1592, pp. 90-106, 1999.] gave a threshold variant of the Cramer-Shoup encryption scheme. Unfortunately, their scheme requires interaction among decryption entities to obtain robustness (i.e., ensure that no coalition of t−1 malicious decryption entities can prevent uncorrupted servers from successfully decrypting) as well as to render invalid ciphertexts harmless. Cramer, Damgård and Ishai suggested [R. Cramer, I. Damgård, Y. Ishai. Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. In TCC'05, Lecture Notes in Computer Science 3378, pp. 342-362, Springer, 2005.] a method to remove the need for interaction but it is only efficient for a small number of entities.
Other threshold variants of Cramer-Shoup were suggested [M. Abe. Robust Distributed Multiplicaton without Interaction. In Crypto'99, Lecture Notes in Computer Science 1666, pp. 130-147, Springer, 1999. and P. MacKenzie. An Efficient Two-Party Public Key Cryptosystem Secure against Adaptive Chosen Ciphertext Attack. In PKC'03, Lecture Notes in Computer Science 2567, pp. 47-61, Springer, 2003.] and Abe notably showed how to achieve optimal resilience (namely, guarantee robustness as long as the adversary corrupts a minority of t<n/2 entities) in the Canetti-Goldwasser system mentioned hereinbefore. In the last decade, generic constructions of CCA-secure threshold cryptosystems with static security were put forth [see Y. Dodis, J. Katz. Chosen-Ciphertext Security of Multiple Encryption. In TCC'05, Lecture Notes in Computer Science 3378, pp. 188-209, Springer, 2005.]
Using the techniques of Canetti-Halevi-Katz [see and R. Canetti, S. Halevi, J. Katz. Chosen-Ciphertext Security from Identity-Based Encryption. In Eurocrypt'04, Lecture Notes in Computer Science 3027, pp. 207-222, Springer, 2004.], Boneh, Boyen and Halevi [D. Boneh, X. Boyen, S. Halevi. Chosen Ciphertext Secure Public Key Threshold Encryption Without Random Oracles. In CT-RSA'06, Lecture Notes in Computer Science 3860, pp. 226-243, Springer, 2006.] gave a fully non-interactive robust CCA-secure threshold cryptosystem with a security proof in the standard model: in their scheme, decryption entities can generate their decryption shares without any communication with other entities. Similar applications of the Canetti-Halevi-Katz methodology to threshold cryptography were also studied [see X. Boyen, Q. Mei, B. Waters. Direct Chosen Ciphertext Security from Identity-Based Techniques. in ACM CCS'05, pp. 320-329, ACM Press, 2005. and E. Kiltz. Chosen-ciphertext security from tag-based encryption. In TCC'06, Lecture Notes in Computer Science 3876, pp. 581-600, Springer, 2006.].
Wee [H. Wee. Threshold and Revocation Cryptosystems via Extractable Hash Proofs. In Eurocrypt '11, Lecture Notes in Computer Science 6632, pp. 589-609, Springer, 2011.] defined a framework allowing to construct non-interactive threshold signatures and (chosen-ciphertext secure) threshold cryptosystems in a static corruption model.
Adaptively Secure Schemes
Most threshold systems (including the ones by Shoup-Gennaro, Canetti-Goldwasser, Dodis-Katz, Boneh-Boyen-Halevi, and [P.-A. Fouque, D. Pointcheval. Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks. In Asiacrypt'01, Lecture Notes in Computer Science 2248, pp. 351-368, Springer, 2001.]) have been analyzed in a static corruption model, where the adversary chooses which entities it wants to corrupt before the scheme is set up. Unfortunately, adaptive adversaries—who can choose whom to corrupt at any time, as a function of their entire view of the protocol execution—are known (see, e.g., R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, T. Rabin. Efficient Multi-Party Computations Secure Against an Adaptive Adversary. In Eurocrypt'99, Lecture Notes in Computer Science 1592, pp. 311-326, Springer, 1999.]) to be strictly stronger.
Assuming reliable erasures, Canetti et al. [R. Canetti, R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin. Adaptive Security for Threshold Cryptosystems. In Crypto'99, Lecture Notes in Computer Science 1666, pp. 98-115, Springer, 1999.] devised adaptively secure protocols for the distributed generation of discrete-logarithm-based keys and DSA signatures. Their techniques were re-used in threshold RSA signatures [see J. Almansa, I. Damgård, J.-B. Nielsen. Simplified Threshold RSA with Adaptive and Proactive Security. In Eurocrypt'06, Lecture Notes in Computer Science 4004, pp. 593-611, Springer, 2006.]. Frankel, MacKenzie and Yung independently showed different methods to achieve adaptive security in the erasure-enabled setting [see Y. Frankel, P. MacKenzie, M. Yung. Adaptively-Secure Distributed Public-Key Systems. In ESA'99, Lecture Notes in Computer Science 1643, pp. 4-27, Springer, 1999. and Y. Frankel, P. MacKenzie, M. Yung. Adaptively-Secure Optimal-Resilience Proactive RSA. In Asiacrypt'99, Lecture Notes in Computer Science 1716, pp. 180-194, Springer, 1999.].
Subsequently, Jarecki and Lysyanskaya [S. Jarecki, A. Lysyanskaya. Adaptively Secure Threshold Cryptography: Introducing Concurrency, Removing Erasures. In Eurocrypt'00, Lecture Notes in Computer Science 1807, pp. 221-242, Springer, 2000.] eliminated the need for erasures and gave an adaptively secure variant of the Canetti-Goldwasser threshold cryptosystem which appeals to interactive zero-knowledge proofs but remains secure in concurrent environments. Unfortunately, their scheme requires a fair amount of interaction among decryption entities. Lysyanskaya and Peikert [A. Lysyanskaya, C. Peikert. Adaptive Security in the Threshold Setting: From Cryptosystems to Signature Schemes. In Asiacrypt'01, Lecture Notes in Computer Science 2248, pp. 331-350, Springer, 2001.] also dealt with adaptive adversaries but their schemes are also interactive. Abe and Fehr [M. Abe, S. Fehr. Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography. In Crypto'04, Lecture Notes in Computer Science 3152, pp. 317-334, Springer, 2004.] showed how to dispense with zero-knowledge proofs in the Jarecki-Lysyanskaya construction so as to prove it secure in (a variant of) the universal composability framework but without completely eliminating interaction from the decryption procedure.
In 2010, Qin et al. [B. Qin, Q. Wu, L. Zhang, J. Domingo-Ferrer. Threshold Public-Key Encryption with Adaptive Security and Short Ciphertexts. In ICICS'10, Lecture Notes in Computer Science 6476, pp. 62-76, Springer, 2010.] suggested a non-interactive threshold cryptosystem (more precisely, a threshold broadcast encryption scheme) with adaptive security. Its downside is its lack of scalability since private key shares consist of O(n) elements, where n is the number of entities (while, in prior schemes, the share size only depends on the security parameter). Moreover, the security proof requires the threshold t to be at most polylogarithmic in the security parameter, even if n is polynomial.
In 2011, Libert and Yung showed [B. Libert, M. Yung. Adaptively Secure Non-Interactive Threshold Cryptosystems. In ICALP 2011, Lecture Notes in Computer Science 6756, pp. 588-600, Springer, 2011.] an adaptively secure variant of the Boneh-Boyen-Halevi construction using groups of composite order. Their scheme is based on a very specific use of the Lewko-Waters techniques [A. Lewko, B. Waters. New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts. In TCC 2010, Lecture Notes in Computer Science 5978, pp. 455-479, Springer, 2010.], which limits its applicability to composite order groups and makes it computationally expensive (not to mention the difficulty of combining it with existing adaptively secure distributed key generation techniques). In 2012, Libert and Yung [B. Libert, M. Yung. Non-Interactive CCA2-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions. In TCC 2012, Lecture Notes in Computer Science 7194, pp. 75-93, Springer, 2012.] described a framework for constructing more efficient non-interactive adaptively secure CCA-secure threshold cryptosystems. However, their most efficient schemes remain significantly less efficient than the standard Cramer-Shoup cryptosystem—which incurs a ciphertext overhead of about 768 bits on carefully chosen elliptic curves for 128 bits of security—for a given security level. In their most efficient construction, ciphertexts are about 3328 bits longer than plaintexts at the 128-bit security level.
It will thus be appreciated that there is a need for a solution that improves the efficiency of the adaptively secure non-interactive constructions in the latter paper by Libert and Yung from bandwidth and computational points of view, while retaining security proofs in the standard model under hardness assumptions of constant size: namely, the number of input elements should not depend on the number of decryption queries made by the adversary. The present invention provides such a solution.